package problems.daily.y2021m6;


import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author habitplus
 * @since 2021-06-28 09:10
 */
public class T20210628N1 {
    // 815. 公交路线
    // 给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
    //
    // 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
    //
    // 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
    // 求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
    // 提示：
    //  1 <= routes.length <= 500.
    //  1 <= routes[i].length <= 105
    //  routes[i] 中的所有值 互不相同
    //  sum(routes[i].length) <= 105
    //  0 <= routes[i][j] < 106
    //  0 <= source, target < 106
    //
    //链接：https://leetcode-cn.com/problems/bus-routes

    public int numBusesToDestination(int[][] routes, int source, int target) {
        // BFS : 对每个公交站点进行枚举
        if (source == target) {
            return 0;
        }
        int n = routes.length;
        // 存储每个公交站点
        Queue<Integer> que = new LinkedList<>();
        // 记录已经坐过的公交车编号
        boolean[] vis = new boolean[n];
        // 对每一辆公交车路线建立 hash 表，便于快速查找公交车所到的站
        Set<Integer>[] list = new HashSet[n];
        Set<Integer> visitedStation = new HashSet<>();
        for (int i = 0; i < n; i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < routes[i].length; j++) {
                set.add(routes[i][j]);
            }
            list[i] = set;
        }

        que.offer(source);
        int res = 0;
        while (!que.isEmpty()) {
            ++res;
            for (int i = que.size(); i > 0; i--) {
                int curStation = que.poll();

                for (int j = 0; j < n; j++) {
                    // 公交车没有坐过，且该公交车包含当前站点
                    if (!vis[j] && list[j].contains(curStation)) {
                        // 该公交车其他站点入队
                        for (int s : list[j]) {
                            if (s != curStation) {
                                que.offer(s);
                            }
                        }

                        visitedStation.addAll(list[j]);
                        vis[j] = true;

                        if (visitedStation.contains(target)) {
                            return res;
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {7,12},{4,5,15},{6},{15,19},{9,12,13}
        };
        System.out.println(new T20210628N1().numBusesToDestination(arr, 15, 12));

    }
}
